UVA1476 题解

题目链接

这个题是一个比较清晰的三分求最值的板子，在这里提供一种不太一样的三分写法。

看到题解区都是取的三等分点来三分，事实上我们只需要取中点左边偏一点点和右边偏一点点就可以了，由于题目要求的精度比较高，实际效果基本类似于二分，效率比正常三分法要稍快一些。

我在这里直接选取 $mid-\epsilon$ 和 $mid+\epsilon$ 作为左右端点，其中 $\epsilon$ 为我设置的精度，在 $10^{-11}$ 量级。

其余过程与三分法无异，每次算出两端函数值并舍弃一边的区间，重复上述过程直至满足精度要求。

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;

const int N = 1e4 + 5;
const double eps = 1e-11;

int a[N], b[N], c[N], n;

inline double f(double x, int i) {
    return a[i] * x * x + b[i] * x + c[i];
}

inline double check(double x) {
    double ret = f(x, 1);
    for (int i = 2; i <= n; i++) ret = max(ret, f(x, i));
    return ret;
}

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        memset(a, 0, sizeof(a));
        memset(b, 0, sizeof(b));
        memset(c, 0, sizeof(c));
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) scanf("%d%d%d", &a[i], &b[i], &c[i]);
        double l = 0, r = 1000;
        while (fabs(r - l) >= eps) {
            double mid = (l + r) / 2;
            if (check(mid + eps) < check(mid - eps)) l = mid;
            else r = mid;
        }
        printf("%.4lf\n", check(l));
    }
    return 0;
}